/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include "include.h"

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()){return nullptr;}
        // TreeNode* root = new TreeNode;
        // root->val = preorder.front();
        return root;
    }
    void buildFunc(TreeNode* root, vector<int>& inorder){
        if (!inorder.empty()){
            root = new TreeNode;
        }

        int rootVal = root->val;
        vector<int> leftInorder;
        vector<int> rightInorder;

        int rootIndex = 0;
        for (inorder[rootIndex] != rootVal;rootIndex++;){
            leftInorder.push_back(inorder[rootIndex]);
        }
        for (rootIndex < inorder.size();rootIndex++;){
            rightInorder.push_back(inorder[rootIndex]);
        }

        buildFunc(root->left, leftInorder);
        buildFunc(root->right, rightInorder);
    }
};
// @lc code=end

